package leetcode.editor.cn;

import java.util.Stack;

//Java：合并二叉树
public class MergeTwoBinaryTrees {
    public static void main(String[] args) {
        Solution solution = new MergeTwoBinaryTrees().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        //这种房四海需要新增节点，递归比较复杂
/*    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode node = new TreeNode();
        if (root1 != null && root2 != null) {
            node.val = root1.val + root2.val;
            node.left = mergeTrees(root1.left, root2.left);
            node.right = mergeTrees(root1.right, root2.right);
        }
        if (root1 != null && root2 == null) {
            node.val = root1.val;
            node.left = mergeTrees(root1.left, null);
            node.right = mergeTrees(root1.right, null);
        }
        if (root2 != null && root1 == null) {
            node.val = root2.val;
            node.left = mergeTrees(null, root2.left);
            node.right = mergeTrees(null, root2.right);
        }
        if (root1 == null && root2 == null) {
            return null;
        }
        return node;
    }*/
        // 递归
/*    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }*/
        // 使用栈迭代
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            if (root1 == null) {
                return root2;
            }
            if (root2 == null) {
                return root1;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root2);
            stack.push(root1);
            while (!stack.isEmpty()) {
                TreeNode node1 = stack.pop();
                TreeNode node2 = stack.pop();
                node1.val += node2.val;
                if (node2.right != null && node1.right != null) {
                    stack.push(node2.right);
                    stack.push(node1.right);
                } else {
                    if (node1.right == null) {
                        node1.right = node2.right;
                    }
                }
                if (node2.left != null && node1.left != null) {
                    stack.push(node2.left);
                    stack.push(node1.left);
                } else {
                    if (node1.left == null) {
                        node1.left = node2.left;
                    }
                }
            }
            return root1;
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}